392. Is Subsequence

Easy

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:
s = "abc", t = "ahbgdc"

Return true.

Example 2:
s = "axc", t = "ahbgdc"

Return false.

Follow up:
If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

1. Iterative

   1) index: str.index(str, beg=0, end=len(string)) 找不到会报错

   2) find: str.find(str, beg=0, end=len(string)) 找不到return -1

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if not s: return True # must match
        if not t: return False # must not match
        
        while(s):
            if not t: return False
            if s[0] in t:
                idx = t.index(s[0])
                t = t[idx+1:] # update the target with rest
                s = s[1:] # update the source with rest
            else:
                return False
        return True

但是我代码有不好的地方是，查了两遍在不在（一次 in，一次.index），对速度会有影响

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        pos = 0
        for c in s:
            try:
                tem = t.index(c, pos)
            except:
                return False
            pos = tem + 1
        return True

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        pos = 0
        for c in s:
            temp = t.find(c, pos)
            if temp == -1:
                return False
            else:
                pos = temp + 1
        return True

2. Off-shelf

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        t = iter(t)
        return all(c in t for c in s)